Cấu trúc của một DHT có thể được phân thành một số thành phần chính.[2][3]

• Nền tảng là một không gian khóa (keyspace) trừu tượng, chẳng hạn tập các xâu kích thước 160-bit.
• Một phương án phân hoạch không gian khóa (keyspace partitioning) chia tách sở hữu không gian khóa này giữa các nút thành viên.
• Một mạng overlay kết nối các nút, cho phép chúng tìm nút chủ của một khóa nào đó trong không gian khóa.

Một khi các thành phần này được lắp ráp vào đúng chỗ, một tình huống điển hình của việc sử dụng DHT cho việc lưu trữ và lấy dữ liệu như sau. Giả sử không gian khóa là một tập các xâu 160-bit. Để lưu trữ một file với t e n _ f i l e {\displaystyle ten\_file} và d u _ l i e u {\displaystyle du\_lieu} cho trước vào DHT, thực hiện băm SHA1 cho t e n _ f i l e {\displaystyle ten\_file} , tạo một khóa k {\displaystyle k} kích thước 160-bit, và thông điệp p u t ( k , d u _ l i e u ) {\displaystyle put(k,du\_lieu)} được gửi tới một nút bất kì tham gia DHT. Thông điệp này được gửi chuyển tiếp từ nút này tới nút khác qua mạng overlay cho đến khi nó đến được nút duy nhất chịu trách nhiệm cho khóa k {\displaystyle k} theo như quy hoạch không gian khóa đã quy định, cặp ( k , d u _ l i e u ) {\displaystyle (k,du\_lieu)} sau đó được lưu trữ tại nút này. Từ đó, một khách hàng bất kì có thể lấy nội dung của file bằng cách lại thực hiện hàm băm cho t e n _ f i l e {\displaystyle ten\_file} để lấy khóa k {\displaystyle k} và yêu cầu một nút DHT bất kì tìm dữ liệu được liên hệ với khóa k {\displaystyle k} bằng một thông điệp g e t ( k ) {\displaystyle get(k)} . Thông điệp này sẽ lại được định tuyến theo mạng overlay để tới được nút chịu trách nhiệm cho khóa k {\displaystyle k} , nút này sẽ trả lời bằng d u _ l i e u {\displaystyle du\_lieu} được lưu trữ tại đó.

Các thành phần phân hoạch không gian khóa và mạng overlay được mô tả ở dưới đây theo các nguyên lý chính thông dụng cho hầu hết các DHT; chi tiết còn tùy theo các thiết kế khác nhau.

Phân hoạch không gian khóa

Đa số các DHT dùng một dạng hàm băm ổn định (consistent hashing) để ánh xạ từ khóa tới các nút. Kĩ thuât này sử dụng một hàm δ ( k 1 , k 2 ) {\displaystyle \delta (k_{1},k_{2})} định nghĩa một khái niệm trừu tượng là khoảng cách từ khóa k 1 {\displaystyle k_{1}} tới khóa k 2 {\displaystyle k_{2}} , khái niệm này không liên quan đến khoảng cách địa lý hay độ trễ mạng. Mỗi nút được gán một khóa đơn, gọi là định danh của nút (ID). Một nút với ID i {\displaystyle i} sở hữu tất cả các khóa mà i {\displaystyle i} là ID gần nhất theo hàm khoảng cách δ {\displaystyle \delta } .

Ví dụ. DHT Chord coi các khóa như là các điểm trên một đường tròn, còn δ ( k 1 , k 2 ) {\displaystyle \delta (k_{1},k_{2})} là độ dài cung tròn nối từ k 1 {\displaystyle k_{1}} tới k 2 {\displaystyle k_{2}} theo chiều kim đồng hồ. Không gian khóa tròn này được phân thành các cung liền nhau, trong đó các điểm mút là định danh của các nút. Nếu i 1 {\displaystyle i_{1}} và i 2 {\displaystyle i_{2}} là hai ID liên tiếp, thì nút với ID i 2 {\displaystyle i_{2}} sở hữu tất cả các khóa nằm giữa i 1 {\displaystyle i_{1}} và i 2 {\displaystyle i_{2}} .

Consistent hashing có tính chất quan trọng rằng việc xóa hay thêm một nút chỉ làm thay đổi tập khóa thuộc sở hữu các nút có ID liền đó, và không ảnh hưởng đến tất cả các nút khác. Tính chất này trái với bảng băm truyền thống mà trong đó việc thêm hoặc bớt một bucket dẫn đến việc phải ánh xạ lại gần như toàn bộ không gian khóa. Do mỗi thay đổi về sở hữu thường tương ứng với một loạt các di chuyển tốn kém về băng thông khi các đối tượng được lưu tại nút này chuyển sang nút khác, việc tối thiểu hóa các hoạt động tái tổ chức như vậy là cần thiết cho việc hỗ trợ có hiệu quả tần suất cao của hiện tượng nút đến và đi.

Mạng nằm ngang

Mỗi nút lưu trữ một tập các liên kết tới các nút khác (danh sách hàng xóm hoặc bảng định tuyến). Các liên kết này tạo nên mạng nằm ngang. Một nút lựa chọn danh sách hàng xóm của mình theo một cấu trúc nhất định, được gọi là photo mạng.

Tất cả các tô pô DHT đều có một biến thể nào đó của tính chất quan trọng nhất: với khóa k {\displaystyle k} bất kì, một nút hoặc có ID sở hữu k {\displaystyle k} hoặc có liên kết tới một nút ở gần k {\displaystyle k} hơn, theo khái niệm khoảng cách không gian khóa được định nghĩa ở trên. Khi đó, có thể dễ dàng định tuyến một thông điệp tới chủ sở hữu của một khóa k {\displaystyle k} bất kì bằng thuật toán ăn tham (thuật toán không nhất thiết tối ưu toàn cục) sau đây: tại mỗi bước, gửi chuyển tiếp thông điệp tới hàng xóm có ID gần k {\displaystyle k} nhất. Khi không có hàng xóm nào như vậy là khi ta đã đến được nút gần nhất—chủ sở hữu của khóa k {\displaystyle k} theo định nghĩa ở trên. Kiểu định tuyến này đôi khi được gọi là định tuyến theo chìa khóa (key based routing).

Vượt ra ngoài tính đúng đắn cơ bản của việc định tuyến, còn có hai ràng buộc quan trọng về photo:

• đảm bảo giữ độ dài tối đa của một tuyến bất kì ở mức thấp, để các yêu cầu có thể được hoàn thành trong thời gian ngắn;
• đảm bảo số hàng xóm tối đa của mỗi nút (bậc tối đa của nút bất kì) ở mức thấp, để chi phí bảo quản không quá cao.

Tất nhiên, để có các tuyến đường ngắn thì cần có bậc tối đa cao. Dưới đây là một số lựa chọn thông dụng cho bậc tối đa và độ dài đường, trong đó n {\displaystyle n} là số nút tham gia DHT:

1. Bậc O ( 1 ) {\displaystyle O(1)} , độ dài đường O ( n ) {\displaystyle O(n)}
2. Bậc O ( log ⁡ n ) {\displaystyle O(\log n)} , độ dài đường O ( log ⁡ n / log ⁡ log ⁡ n ) {\displaystyle O(\log n/\log \log n)}
3. Bậc O ( log ⁡ n ) {\displaystyle O(\log n)} , độ dài đường O ( log ⁡ n ) {\displaystyle O(\log n)}
4. Bậc O ( n ) {\displaystyle O({\sqrt {n}})} , độ dài đường O ( 1 ) {\displaystyle O(1)}

Lựa chọn thứ ba là thông dụng nhất, tuy không tối ưu lắm về tương quan giữa bậc và độ dài đường, vì các tô pô như vật thường cho phép lựa chọn hàng xóm một cách mềm dẻo hơn. Nhiều DHT sử dụng sự mềm dẻo đó để chọn hàng xóm ở gần theo nghĩa độ trễ của mạng vật lý bên dưới.

Các thuật toán cho mạng overlay

Bên cạnh các thuật toán định tuyến, có nhiều thuật toán khai thác cấu trúc của mạng overlay cho việc gửi thông điệp tới tất các nút hoặc một tập con các nút của một DHT.[4] Các thuật toán này được sử dụng trong các ứng dụng để gửi lan truyền multicast, range queries, hoặc để thu thập thống kê.